\documentclass[a4paper]{article}

%\usepackage{a4wide}

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[pdftex]{graphicx}
\usepackage{longtable}
\usepackage{hyperref}
\usepackage[portuguese]{babel}
\usepackage{float}
\usepackage{listings}
\usepackage{makeidx}  % allows for indexgeneration
\usepackage{times}

\begin{document}

\setcounter{page}{2}

\section*{Objectivo}

Este trabalho têm por objectivo criar uma implementação do jogo Hex de
forma a que o computador utilize vários algoritmos de inteligência
artificial ao efectuar as suas jogadas.

A linguagem usada para a implementação deste trabalho será a linguagem
Java.

Para efeitos de inteligência artificial, irá ser inicialmente
utilizado o algoritmo Mi\-ni\-max com cortes Alfa-Beta, podendo no entanto
serem utilizados futuramente outros algoritmos para se poder comparar
os resultados obtidos.

O jogo deverá ter uma interface gráfica onde o utilizador poderá ver o
estado actual do tabuleiro, bem como efectuar a sua jogada.

Nesta interface o utilizador poderá também conseguir seleccionar os
diferentes modos de jogo: humano contra humano, humano contra
computador e computador contra computador. Deverá ser também possível
ajustar os níveis de dificuldade dos jogadores do computador, bem como
o tamanho do tabuleiro a usar.

\section*{Descrição}

\subsection*{Especificação}

Nesta secção do relatório iremos descrever a forma como o trabalho vai
ser implementado.

Este trabalho será dividido nas seguintes etapas:


\begin{enumerate}
  \item Estudo das regras do jogo e das suas heurísticas;
  \item Criação do código que será usado para definir um tabuleiro;
  \item Criação de uma interface em modo texto;
  \item Criação do algoritmo para verificar o final do jogo;
  \item Testar o programa através de vários jogos contra o computador,
    estando este a usar um algoritmo aleatório para fazer as suas
    decisões;
  \item Criação da interface gráfica;
  \item Criação do algoritmo Minimax com cortes Alfa-Beta.
\end{enumerate}

Algumas destas etapas irão ser executadas em paralelo, tais como a etapa 5 e a etapa 6.

Serão agora descritas com maior detalhe cada uma das etapas do trabalho.

\subsubsection*{Estudo das regras do jogo e das suas heurísticas}

Como nenhum dos membros do grupo está familiarizado com as regras do
jogo a implementar, é necessário efectuar algumas pesquisas para se
ficar a conhecer as suas regras.

Nesta pesquisa, também deverão ser estudadas as heurísticas que podem
ser utilizadas pelo algoritmo Minimax de forma a tornar o computador
um oponente mais forte.

\subsubsection*{Criação do código que será usado para definir um tabuleiro}

Como pré-requisito para se poder começar a implementar a inteligência
artificial no computador é necessário que já esteja definido no
trabalho o código fonte para criar um tabuleiro.

Como se pode observar na Fig \ref{fig:tabuleiro_hex_10x10}, as casas
do tabuleiro têm um aspecto hexagonal. Como tal, para o tabuleiro ser
representado num array de arrays, será necessário determinar as regras
que indicarão quais as casas que se encontram ligadas a uma dada casa.


\begin{figure}[htb]
  
  \begin{center}
    \includegraphics[scale=0.5]{hex.png}
    \caption{Aspecto de um tabuleiro Hex 10x10}
    \label{fig:tabuleiro_hex_10x10}
  \end{center}

\end{figure}


Para simplificar o raciocínio, vamos considerar um tabuleiro de 3
casas por 3 casas, como o que está representado na Fig
\ref{fig:tabuleiro_hex_3x3}.

Uma possível representação deste tabuleiro seria a seguinte:

\begin{verbatim}
1 ---> [[1,0,1,0,1,0,0],
2 --->  [0,1,0,1,0,1,0],
3 --->  [0,0,1,0,1,0,1]]
              \   \   \
               A   B   C
\end{verbatim}

Neste caso, os 0 representam casa não válidas e os 1 representam casas
vazias. Os 0 ajudam a representar o formato do tabuleiro no array,
isto é, se ignorarmos os 0, o tabuleiro teria este aspecto:

\begin{verbatim}
1 ---> [[1 1 1  ],
2 --->  [ 1 1 1 ],
3 --->  [  1 1 1]]
            \ \ \
             A B C
\end{verbatim}

No entanto, ao observar este formato do tabuleiro, é possível ver que
o tabuleiro pode ser representado sem ser necessário usar as casas não
válidas. Ou seja, o tabuleiro pode ser representado da seguinte forma:

\begin{verbatim}
1 ---> [[1,1,1],
2 --->  [1,1,1],
3 --->  [1,1,1]]
         | | |
         A B C
\end{verbatim}

\begin{figure}[t]
  
  \begin{center}
    \includegraphics[scale=0.5]{hex-board-3x3.png}
    \caption{Tabuleiro Hex 3x3}
    \label{fig:tabuleiro_hex_3x3}
  \end{center}

\end{figure}

Para um tabuleiro ser representado neste formato é, no entanto,
necessário determinar quais as casas do tabuleiro que estão ligadas
entre si e qual a sua representação neste formato.

Nos exemplos da Fig \ref{fig:tabuleiros_hex_caminhos}, está mostrado
as ligações entre as casas todas de um ta\-bu\-leiro de 3 por 3, bem como
a sua representação interna no programa. A peça preta (representadas
por um 3 na representação interna) representa a casa que se está a
considerar, as peças vermelhas (representada por um 2 na representação
interna) indicam as casas que estão ligadas a esta. Na representação
interna as casas vazias são representadas pelo 1.

\begin{figure}[htb]
  
  \begin{center}
    \includegraphics[width=\linewidth]{tabuleiros_hex.png}
    \caption{Ligações entre as casas do tabuleiro}
    \label{fig:tabuleiros_hex_caminhos}
  \end{center}

\end{figure}


De notar que o tabuleiro poderá ser criado com diversos tamanhos, que
serão indicados na interface do programa, porém, o tabuleiro terá
sempre o mesmo número de casas quer em comprimento, quer em altura.

\subsubsection*{Criação de uma interface em modo texto}

Para efeitos de testes de algoritmos do programa, deverá ser criada
uma simples interface em modo texto que permita ao utilizador fazer um
jogo completo contra o computador.

Esta interface deverá também permitir a escolha dos diferentes
algoritmos que o computador pode usar, bem como permitir ao utilizador
escolher o tamanho do ta\-bu\-leiro a ser usado e o tipo de jogo.

\subsubsection*{Criação do algoritmo para verificar o final do jogo}

No jogo Hex, um jogador joga com as peças do tipo ``horizontal'',
enquanto que o seu oponente joga com as peças do tipo ``vertical'',
sendo o objectivo do jogo a criação de um caminho que toque nos dois
respectivos lados do tabuleiro, ou seja, o jogador com as peças do
tipo ``horizontal'' tem que fazer um caminho de peças que ligue o lado
esquerdo do tabuleiro com o lado direito, enquanto que o jogador com
as peças do tipo ``vertical'' tem que fazer um caminho que ligue o topo
do tabuleiro ao fundo do mesmo.

Como tal, deverá ser criado um algoritmo que consiga detectar caminhos
que toquem em lados opostos do tabuleiro.

\subsubsection*{Testar o programa através de vários jogos contra o computador, estando este a usar um algoritmo aleatório para fazer as suas decisões}

Durante esta fase deverá ser implementado uma inteligência artificial
que faça decisões aleatórias. Esta inteligência artificial, juntamente
com a interface em modo texto permitirá testar o tabuleiro do jogo,
bem como o algoritmo de verificação do final de jogo.

No final desta fase do trabalho, deverá ser possível ao utilizador
realizar jogos completos e de diferentes tipos.

\subsubsection*{Criação da interface gráfica}

Nesta fase será criada uma interface gráfica que permitirá ao
utilizador interagir com o programa de forma mais intuitiva que a
interface em modo texto. Esta interface gráfica deverá permitir
realizar todas as acções que eram possíveis na interface em modo de
texto, ou seja, deverá ser possível definir o tamanho do tabuleiro a
usar e o tipo de jogo.

\subsubsection*{Criação do algoritmo Minimax com cortes Alfa-Beta}

Nesta fase, o algoritmo aleatório usado para a inteligência artificial
do computador será substituido por um algoritmo Minimax com cortes
Alfa-Beta.

\subsection*{Trabalho Efectuado}

Neste momento já está efectuado o estudo das regras do jogo e a
escolha das heurísticas a utilizar (etapa 1 do trabalho), bem como a
criação do código que será usado para definir um tabuleiro (etapa 2 do
trabalho).

Estão neste momento a ser implementadas uma interface em modo texto
(etapa 3 do trabalho) e o algoritmo para verificação do final de um
jogo (etapa 4 do trabalho).

\subsection*{Resultados esperados e forma de avaliação}

No final deste trabalho deverá existir um programa que permita testar
diversos algoritmos de inteligência artificial aplicados ao jogos com
oponentes no contexto do jogo Hex.

Esses algoritmos serão avaliados através da execução de jogos contra o
utilizador e contra outros algoritmos, podendo-se assim observar qual
dos algoritmos é mais forte.

\section*{Conclusões}

Como o jogo Hex é um jogo simples em termos de regras, a sua
implementação irá permitir-nos concentrar na implementação e estudo
dos algoritmos de inteligência artificial e não na implementação das
suas regras.

Por esta razão as etapas iniciais do trabalho concentram-se em
implementar, o mais rapidamente possível, uma interface simples em
modo texto que permita testar as regras do jogo, para que se possa
depois implementar e testar os algoritmos de inteligência artificial.

\section*{Recursos}

\url{http://www.hexwiki.org/index.php?title=Basic_%28strategy_guide%29}

\noindent\url{http://matematica.no.sapo.pt/hex/hex.html}

\noindent\url{http://brainwagon.org/wp-content/uploads/2008/05/hex.png}

\end{document}
